package com.dyz.leetcode._04_bitOperation;

public class _29_divide {
    public int divide(int dividend, int divisor) {
        int sign = 1;
        if((dividend<0 && divisor>0) ||(dividend>0 && divisor<0)){
            sign = -1;
        }
        if(dividend==Integer.MIN_VALUE && divisor==-1){
            return Integer.MAX_VALUE;
        }
        if(dividend>0){dividend = -dividend;}
        if(divisor>0){divisor = -divisor;}
        int res = 0;
        while(dividend<=divisor){
            dividend-=divisor;
            res++;
        }
        return sign*res;
    }

    // 时间复杂度：O(logn * logn)，n 是最大值 2147483647 --> 10^10
    public int divide1(int dividend, int divisor) {
        int sign = 1;
        if((dividend<0 && divisor>0) ||(dividend>0 && divisor<0)){
            sign = -1;
        }
        if(dividend==Integer.MIN_VALUE && divisor==-1){
            return Integer.MAX_VALUE;
        }
        if(dividend>0){dividend = -dividend;}
        if(divisor>0){divisor = -divisor;}
        int res = 0;
        while(dividend<=divisor){
            int k = 1;
            int value = divisor;
            // 0xc0000000 是十进制 -2^30 的十六进制的表示
            // 判断 value >= 0xc0000000 的原因：保证 value + value 不会溢出
            // 可以这样判断的原因是：0xc0000000 是最小值 -2^31 的一半，
            // 而 a 的值不可能比 -2^31 还要小，所以 value 不可能比 0xc0000000 小
            // -2^31 / 2 = -2^30
            while(value>=0xc0000000 &&  dividend<value+value){
                value += value;
                k += k;
            }
            dividend -= value;
            res+=k;

        }
        return sign*res;
    }
    // 时间复杂度：O(1)
    public int divide3(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1){
            return Integer.MAX_VALUE;}
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;
        a = Math.abs(a);
        b = Math.abs(b);
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            // 首先，右移的话，再怎么着也不会越界
            // 其次，无符号右移的目的是：将 -2147483648 看成 2147483648

            // 注意，这里不能是 (a >>> i) >= b 而应该是 (a >>> i) - b >= 0
            // 这个也是为了避免 b = -2147483648，如果 b = -2147483648
            // 那么 (a >>> i) >= b 永远为 true，但是 (a >>> i) - b >= 0 为 false
            if ((a >>> i) - b >= 0) { // a >= (b << i)
                a -= (b << i);
                res += (1 << i);
            }
        }
        // bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
        return sign == 1 ? res : -res;
    }
}
